#!/usr/bin/python
# -*- coding: utf-8 -*-

'''
Introduction to Programming in Java - An Interdisciplinary Approach

All book programs ported to Python by
Scott C. King (revisionx at {gee}ma1l <dot> c0m).

All program examples pass Pylint with a perfect 10.00 score.
Pylint:  http://www.pylint.org/


Exercise 1.4.33 - Random walkers

Random walkers. Suppose that N random walkers, starting in the center
of an N-by-N grid, move one step at a time, choosing to go left, right,up,
or down with equal probability at each step. Write a program to help
formulate and test a hypothesis about the number of step staken
before all cells are touched.

Syntax:
python randomwalkers.py 10


Notes:
int(sys.argv[1]) == Integer.parseInt(args[0])

sys is a required import here in order to use command line arguments.
https://docs.python.org/2/tutorial/stdlib.html

random is a required import as a substitute for Java's Math.random()
https://docs.python.org/2/library/random.html

'''

import sys
import random


def step_test(matrix):
    ''' walk a matrix, return true/false based on population '''

    for row in range(len(matrix)):
        for col in range(len(matrix)):
            if not matrix[row][col]:
                return False
    return True


def main():
    ''' N walkers roam N-by-N grid until all cells touched '''

    try:
        walkers = int(sys.argv[1])
    except IndexError:
        print 'An integer for number of walkers/grid size is required.'
        print 'Ex:  10 walkers walking in a 10 x 10 grid.'
        print 'Syntax: "python randomwalkers.py 10'
        sys.exit(0)

    the_grid = [[False for _ in range(walkers)] for _ in range(walkers)]
    point_x = walkers / 2
    point_y = walkers / 2

    # tracker array keeps track of walker positions in the grid
    tracker = []
    for walker in range(0, walkers):
        new_array = [point_x, point_y]
        tracker.append(new_array)

    steps = 0
    populated = False
    while not populated:
        for walker in range(0, len(tracker)):

            # Test to see if all locations reached
            populated = step_test(the_grid)
            if populated:
                break

            # Walker takes random step left, right, forward, back
            rand = random.random()
            if rand < .25 and tracker[walker][0] < (walkers - 1):
                tracker[walker][0] += 1
            elif rand < .50 and tracker[walker][0] > 0:
                tracker[walker][0] -= 1
            elif rand < .75 and tracker[walker][1] < (walkers - 1):
                tracker[walker][1] += 1
            elif rand < 1.00 and tracker[walker][1] > 0:
                tracker[walker][1] -= 1

            # Reconcile walker x, y position with the grid
            if not the_grid[(tracker[walker][0])][(tracker[walker][1])]:
                the_grid[(tracker[walker][0])][(tracker[walker][1])] = True

            # increment number of steps taken
            steps += 1


    print 'All positions touched in {} steps.'.format(steps)


if __name__ == '__main__':
    main()
